home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / share / pyshared / checkbox / resolver.py < prev    next >
Encoding:
Python Source  |  2009-04-27  |  3.7 KB  |  107 lines
  1. #
  2. # This file is part of Checkbox.
  3. #
  4. # Copyright 2008 Canonical Ltd.
  5. #
  6. # Checkbox is free software: you can redistribute it and/or modify
  7. # it under the terms of the GNU General Public License as published by
  8. # the Free Software Foundation, either version 3 of the License, or
  9. # (at your option) any later version.
  10. #
  11. # Checkbox is distributed in the hope that it will be useful,
  12. # but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. # GNU General Public License for more details.
  15. #
  16. # You should have received a copy of the GNU General Public License
  17. # along with Checkbox.  If not, see <http://www.gnu.org/licenses/>.
  18. #
  19. class Resolver:
  20.     """
  21.     Main class. Instantiate with the root directory of your names.
  22.     """
  23.  
  24.     def __init__(self, cmp=None):
  25.         self.cmp = cmp
  26.  
  27.         # detect repeated resolution attempts - these indicate some circular dependency
  28.         self.reentrant_resolution = set()
  29.  
  30.         # for each script, keep a set of dependencies
  31.         self.dependencies = {}
  32.  
  33.         # collect all names underneath root directory
  34.         self.names = {}
  35.  
  36.     def add(self, name, *dependencies):
  37.         if name in self.names:
  38.             raise Exception, "%s: name already exists" % name
  39.         self.names[name] = set(dependencies)
  40.  
  41.     def remove(self, name):
  42.         del self.names[name]
  43.  
  44.     def resolve(self, name, found=None):
  45.         """
  46.         the center piece.
  47.         recursively resolve dependencies of scripts
  48.         return them as a flat list, sorted according to ancestral relationships
  49.         """
  50.         resolved = self.dependencies.get(name, None)
  51.         if resolved is not None:
  52.             return resolved
  53.  
  54.         if name not in self.names:
  55.             msg = "no dependencies found for %s" % name
  56.             if found:
  57.                 msg += " while resolving %s" % found
  58.             raise Exception, msg
  59.  
  60.  
  61.         dependencies = self.names.get(name)
  62.         resolved = set()
  63.  
  64.         for dependency in dependencies:
  65.             resolution_step = (name, dependency)
  66.             if resolution_step in self.reentrant_resolution:
  67.                 if found:
  68.                     scapegoat = found
  69.                 else:
  70.                     scapegoat = dependency
  71.                 raise Exception, "circular dependency involving %s and %s" % (name, scapegoat)
  72.             self.reentrant_resolution.add(resolution_step)
  73.             resolved.update(self.resolve(dependency, found=name)) # and its dependencies, if any
  74.  
  75.         # now it's time for sorting hierarchically... Since circular dependencies are excluded,
  76.         # ancestors will always have fewer dependencies than descendants, so sorting by the
  77.         # number of dependencies will give the desired order.
  78.         resolved = sorted(resolved, key=lambda x : len(self.dependencies[x]))
  79.         resolved.append(name)
  80.         self.dependencies[name] = resolved
  81.  
  82.         return resolved
  83.  
  84.     def get_dependencies(self, name):
  85.         return self.resolve(name)
  86.  
  87.     def get_dependents(self, name=None):
  88.         dependents = []
  89.         if name:
  90.             # Immediate dependents
  91.             all_dependents = filter(lambda x : name in self.resolve(x)[:-1], self.names)
  92.             dependents = filter(lambda x : self.get_dependencies(x)[-2] == name, all_dependents)
  93.         else:
  94.             # First level of dependents
  95.             dependents = filter(lambda x : len(self.resolve(x)) == 1, self.names)
  96.  
  97.         index = 0
  98.         dependents = sorted(dependents, self.cmp)
  99.         while index < len(dependents):
  100.             sub_dependents = self.get_dependents(dependents[index])
  101.             if sub_dependents:
  102.                 dependents[index+1:index+1] = sub_dependents
  103.                 index += len(sub_dependents)
  104.             index += 1
  105.  
  106.         return dependents
  107.